{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Costs Using the Train Line"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minimumCosts"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #乘坐火车路线的最少费用"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>城市中的火车有两条路线，分别是常规路线和特快路线。两条路线经过 <strong>相同 </strong>的 <code>n + 1</code> 个车站，车站编号从 <code>0</code> 到 <code>n</code>。初始时，你位于车站 <code>0</code> 的常规路线。</p>\n",
    "\n",
    "<p>给你两个<strong> 下标从 1 开始 </strong>、长度均为 <code>n</code> 的两个整数数组 <code>regular</code> 和 <code>express</code> ，其中 <code>regular[i]</code> 表示乘坐常规路线从车站&nbsp;<code>i - 1</code> 到车站&nbsp;<code>i</code> 的费用，<code>express[i]</code> 表示乘坐特快路线从车站&nbsp;<code>i - 1</code> 到车站&nbsp;<code>i</code> 的费用。</p>\n",
    "\n",
    "<p>另外给你一个整数 <code>expressCost</code>，表示从常规路线转换到特快路线的费用。</p>\n",
    "\n",
    "<p>注意：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>从特快路线转换回常规路线没有费用。</li>\n",
    "\t<li><strong>每次 </strong>从常规路线转换到特快路线，你都需要支付 <code>expressCost</code> 的费用。</li>\n",
    "\t<li>留在特快路线上没有额外费用。</li>\n",
    "</ul>\n",
    "\n",
    "<p>返回<strong> 下标从 1 开始</strong> 、长度为 <code>n</code> 的数组 <code>costs</code>，其中 <code>costs[i]</code> 是从车站 <code>0</code> 到车站 <code>i</code> 的最少费用。</p>\n",
    "\n",
    "<p>注意：每个车站都可以从任意一条路线 <strong>到达 </strong>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/07/25/ex1drawio.png\" style=\"width: 442px; height: 150px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>regular = [1,6,9,5], express = [5,2,3,10], expressCost = 8\n",
    "<strong>输出：</strong>[1,7,14,19]\n",
    "<strong>解释：</strong>上图展示了从车站 0 到车站 4 的最少费用方法。\n",
    "- 乘坐常规路线从车站 0 到车站 1，费用是 1。\n",
    "- 乘坐特快路线从车站 1 到车站 2，费用是 8 + 2 = 10。\n",
    "- 乘坐特快路线从车站 2 到车站 3，费用是 3。\n",
    "- 乘坐特快路线从车站 3 到车站 4，费用是 5。\n",
    "总费用是 1 + 10 + 3 + 5 + 19。\n",
    "注意到达其他车站的最少费用方法可以选择不同的路线。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/07/25/ex2drawio.png\" style=\"width: 346px; height: 150px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>regular = [11,5,13], express = [7,10,6], expressCost = 3\n",
    "<strong>输出：</strong>[10,15,24]\n",
    "<strong>解释：</strong>上图展示了从车站 0 到车站 3 的最少费用方法。\n",
    "- 乘坐特快路线从车站 0 到车站 1，费用是 3 + 7 = 10。\n",
    "- 乘坐常规路线从车站 1 到车站 2，费用是 5。\n",
    "- 乘坐特快路线从车站 2 到车站 3，费用是 3 + 6 = 9。\n",
    "总费用是 10 + 5 + 9 = 24。\n",
    "注意转换回特快路线时需要再次支付 expressCost 的费用。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == regular.length == express.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= regular[i], express[i], expressCost &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-costs-using-the-train-line](https://leetcode.cn/problems/minimum-costs-using-the-train-line/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-costs-using-the-train-line](https://leetcode.cn/problems/minimum-costs-using-the-train-line/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,6,9,5]\\n[5,2,3,10]\\n8', '[11,5,13]\\n[7,10,6]\\n3']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "    Dynamic programming.\n",
    "    Let\n",
    "        dp[i][0] = the min cost to reach stop i on the regular route, and\n",
    "        dp[i][1] = the min cost to reach stop i on the express route. \n",
    "    We have,\n",
    "        dp[i][0] = min(dp[i-1][0] + regular[i-1], dp[i-1][1] + regular[i-1]), and\n",
    "        dp[i][1] = min(dp[i-1][1] + express[i-1], dp[i-1][0] + expressCost + express[i-1]).\n",
    "    Time complexity: O(n). Space complexity: O(1) (not counting the output array).\n",
    "    '''\n",
    "    def minimumCosts(self, regular: List[int], express: List[int], expressCost: int) -> List[int]:\n",
    "        dp_0_prev, dp_1_prev = 0, expressCost # dp[i-1][0], dp[i-1][1]\n",
    "        ans = [-1] * len(regular)\n",
    "        for i in range(1, len(regular)+1):\n",
    "            dp_0 = min(dp_0_prev + regular[i-1], dp_1_prev + regular[i-1]) # dp[i][0]\n",
    "            dp_1 = min(dp_1_prev + express[i-1], dp_0_prev + expressCost + express[i-1]) # dp[i][1]\n",
    "            ans[i-1] = min(dp_0, dp_1)\n",
    "            dp_0_prev, dp_1_prev = dp_0, dp_1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCosts1(self, regular: List[int], express: List[int], expressCost: int) -> List[int]:\n",
    "        a, b, res = 0, expressCost, []\n",
    "        for i, j in zip(regular, express):\n",
    "            a, b = a + i, b + j\n",
    "            if a > b: a = b\n",
    "            elif b > a + expressCost: b = a + expressCost\n",
    "            res.append(min(a,b))\n",
    "        return res\n",
    "        \n",
    "\n",
    "    def minimumCosts(self, regular: List[int], express: List[int], expressCost: int) -> List[int]:\n",
    "        a, b, res = 0, expressCost, []\n",
    "        for i, j in zip(regular, express):\n",
    "            a, b = min(a + i, b + j), min(b + j, a + i + expressCost)\n",
    "            res.append(min(a,b))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "    Dynamic programming.\n",
    "    Let\n",
    "        dp[i][0] = the min cost to reach stop i on the regular route, and\n",
    "        dp[i][1] = the min cost to reach stop i on the express route. \n",
    "    We have,\n",
    "        dp[i][0] = min(dp[i-1][0] + regular[i-1], dp[i-1][1] + regular[i-1]), and\n",
    "        dp[i][1] = min(dp[i-1][1] + express[i-1], dp[i-1][0] + expressCost + express[i-1]).\n",
    "    Time complexity: O(n). Space complexity: O(1) (not counting the output array).\n",
    "    '''\n",
    "    def minimumCosts(self, regular: List[int], express: List[int], expressCost: int) -> List[int]:\n",
    "        dp_0_prev, dp_1_prev = 0, expressCost # dp[i-1]\n",
    "        dp_0, dp_1 = 0, 0 # dp[i]\n",
    "        ans = [-1] * len(regular)\n",
    "        for i in range(1, len(regular)+1):\n",
    "            dp_0 = min(dp_0_prev + regular[i-1], dp_1_prev + regular[i-1])\n",
    "            dp_1 = min(dp_1_prev + express[i-1], dp_0_prev + expressCost + express[i-1])\n",
    "            ans[i-1] = min(dp_0, dp_1)\n",
    "            dp_0_prev, dp_1_prev = dp_0, dp_1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCosts(self, regular: List[int], express: List[int], expressCost: int) -> List[int]:\n",
    "        n = len(regular)\n",
    "        ans1 = [0] * (n + 1)\n",
    "        ans2 = [0] * (n + 1)\n",
    "        ans = [0] * n\n",
    "        ans2[0] = expressCost\n",
    "        for i in range(n):\n",
    "            ans1[i + 1] = min(ans1[i] + regular[i], ans2[i] + regular[i], ans2[i] + express[i])\n",
    "            ans2[i + 1] = min(ans1[i] + regular[i] + expressCost, ans2[i] + express[i], ans1[i] + expressCost + express[i])\n",
    "            ans[i] = min(ans1[i + 1], ans2[i + 1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCosts(self,regular:List[int],express:List[int],expressCost: int)->List[int]:\n",
    "        INF=0x3f3f3f3f3f3f3f3f\n",
    "        n=len(regular)\n",
    "        dp1=[INF]*(n+1)\n",
    "        dp2=[INF]*(n+1)\n",
    "        cost=[0]*n\n",
    "        dp1[0]=0\n",
    "        dp2[0]=expressCost\n",
    "        for i in range(1,n+1):\n",
    "            dp1[i]=min(dp1[i-1],dp2[i-1])+regular[i-1]\n",
    "            dp2[i]=min(dp2[i-1],dp1[i-1]+expressCost)+express[i-1]\n",
    "            cost[i-1]=min(dp1[i],dp2[i])\n",
    "        return cost"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCosts(self, regular: List[int], express: List[int], expressCost: int) -> List[int]:\n",
    "        #dp[2][n + 1]\n",
    "        #dp[0]: cost for arriving at a station using regular\n",
    "        #dp[1]: cost for arriving at a station using express\n",
    "        dp = [[float('inf')]*(len(regular)) for _ in range(2)]\n",
    "        res = [float('inf')] * (len(regular))\n",
    "        dp[1][0] = expressCost + express[0]\n",
    "        summ = 0\n",
    "        \n",
    "        for i in range(len(regular)):\n",
    "            summ += regular[i]\n",
    "            p = regular[i]\n",
    "            if i - 1 >= 0:\n",
    "                p += min(dp[0][i - 1] , dp[1][i - 1])\n",
    "            dp[0][i] = p\n",
    "            dp[1][i] = min(dp[1][i] , dp[0][i] + expressCost , dp[1][i - 1] + express[i])\n",
    "        for i in range(len(regular)):\n",
    "            res[i] = min(dp[0][i] , dp[1][i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCosts(self, regular: List[int], express: List[int], expressCost: int) -> List[int]:\n",
    "\n",
    "        n = len(regular)\n",
    "        dp = [[0]*2 for _ in range(n+1)]\n",
    "\n",
    "        dp[0][1] = expressCost\n",
    "\n",
    "        ans = []\n",
    "        for i in range(1,n+1):\n",
    "            dp[i][0] = min(dp[i-1][0]+regular[i-1], dp[i-1][1]+express[i-1])\n",
    "            dp[i][1] = min(dp[i-1][0]+regular[i-1]+expressCost,\n",
    "                                dp[i-1][1]+express[i-1])\n",
    "            ans.append(min(dp[i]))\n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCosts(self, regular: List[int], express: List[int], expressCost: int) -> List[int]:\n",
    "        \"\"\" dfs(curr_i, lineType. des): the minimum cost so far at station curr_i \n",
    "        and line type of lineType with destibation des \n",
    "        \"\"\"\n",
    "\n",
    "        # TLE solution \n",
    "        # @functools.lru_cache(None)\n",
    "        # def dfs(curr_i, j, des):\n",
    "        #     if curr_i == des:\n",
    "        #         return 0 \n",
    "            \n",
    "        #     res = 0 \n",
    "        #     # no switch of the state \n",
    "        #     if j == 0:\n",
    "        #         S1 = dfs(curr_i+1, j, des) + regular[curr_i]\n",
    "        #     elif j == 1:\n",
    "        #         S1 = dfs(curr_i+1, j, des) + express[curr_i]\n",
    "        #     # switch the state \n",
    "        #     if j == 0:\n",
    "        #         S2 = dfs(curr_i+1, 1, des) + express[curr_i] + expressCost\n",
    "        #     elif j == 1:\n",
    "        #         S2 = dfs(curr_i+1, 0, des) + regular[curr_i]\n",
    "        #     res += min(S1, S2)\n",
    "        #     return res \n",
    "\n",
    "        # ans = []\n",
    "        # n_stations = len(regular)\n",
    "        # for des in range(1, n_stations+1):\n",
    "        #     ans.append(dfs(0, 0, des))  \n",
    "        #     dfs.cache_clear()\n",
    "\n",
    "        # return ans \n",
    "\n",
    "        \n",
    "        # DP solution \n",
    "        n = len(regular)\n",
    "        cost = [ [0, 0] for _ in range(n+1) ]\n",
    "        cost[0][1] = expressCost  # additional fee for switching the line \n",
    "\n",
    "        # running dp \n",
    "        for i in range(1, n+1):\n",
    "            cost[i][0] = min(\n",
    "                cost[i-1][0] + regular[i-1],\n",
    "                cost[i-1][1] + regular[i-1]\n",
    "            )\n",
    "            cost[i][1] = min(\n",
    "                cost[i][0] + expressCost,\n",
    "                cost[i-1][1] + express[i-1]\n",
    "            )\n",
    "\n",
    "        return [min(c) for c in cost[1:]]\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCosts(self, regular: List[int], express: List[int], expressCost: int) -> List[int]:\n",
    "        \"\"\" dfs(curr_i, lineType. des): the minimum cost so far at station curr_i \n",
    "        and line type of lineType with destibation des \n",
    "        \"\"\"\n",
    "\n",
    "        # TLE solution \n",
    "        # @functools.lru_cache(None)\n",
    "        # def dfs(curr_i, j, des):\n",
    "        #     if curr_i == des:\n",
    "        #         return 0 \n",
    "            \n",
    "        #     res = 0 \n",
    "        #     # no switch of the state \n",
    "        #     if j == 0:\n",
    "        #         S1 = dfs(curr_i+1, j, des) + regular[curr_i]\n",
    "        #     elif j == 1:\n",
    "        #         S1 = dfs(curr_i+1, j, des) + express[curr_i]\n",
    "        #     # switch the state \n",
    "        #     if j == 0:\n",
    "        #         S2 = dfs(curr_i+1, 1, des) + express[curr_i] + expressCost\n",
    "        #     elif j == 1:\n",
    "        #         S2 = dfs(curr_i+1, 0, des) + regular[curr_i]\n",
    "        #     res += min(S1, S2)\n",
    "        #     return res \n",
    "\n",
    "        # ans = []\n",
    "        # n_stations = len(regular)\n",
    "        # for des in range(1, n_stations+1):\n",
    "        #     ans.append(dfs(0, 0, des))  \n",
    "        #     dfs.cache_clear()\n",
    "\n",
    "        # return ans \n",
    "\n",
    "        \n",
    "        # DP solution \n",
    "        n = len(regular)\n",
    "        cost = [ [0, 0] for _ in range(n+1) ]\n",
    "        cost[0][1] = expressCost  # additional fee for switching the line \n",
    "\n",
    "        # running dp \n",
    "        for i in range(1, n+1):\n",
    "            cost[i][0] = min(\n",
    "                cost[i-1][0] + regular[i-1],\n",
    "                cost[i-1][1] + regular[i-1]\n",
    "            )\n",
    "            cost[i][1] = min(\n",
    "                cost[i][0] + expressCost,\n",
    "                cost[i-1][1] + express[i-1]\n",
    "            )\n",
    "\n",
    "        return [min(c) for c in cost[1:]]\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCosts(self, regular: List[int], express: List[int], expressCost: int) -> List[int]:\n",
    "        n = len(regular)\n",
    "        # 因为最终要返回的是一个从1开始到n的min值，也就是n个pair的最小值构成的list\n",
    "        dp = [[0, 0] for i in range(n+1)]\n",
    "        dp[0][1] = expressCost\n",
    "        dp[0][0] = 0\n",
    "        for i in range(1, n+1):\n",
    "            dp[i][0] = min(dp[i-1][0] + regular[i-1], dp[i-1][1] + express[i-1])\n",
    "            dp[i][1] = min(dp[i][0] + expressCost, dp[i-1][1] + express[i-1])\n",
    "        return [min(cost) for cost in dp[1:]]"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
